/**
 * File:    ThinningAlgorithm.cpp
 * Author:  Bui Quang Anh
 * Email:   quang_anh.bui@univ-lr.fr
 * Version: 1.0
 * 
 * DESCRIPTION:
 * Implementation file for class ThinningAlgorithm.
 * Provide algorithms for image skeletonization and half skeletonization
 * 
 * CHANGE HISTORY:
 * (13/10/2011 15:10) File first time created - BUI Quang Anh
 * (14/10/2011 12:46) Implementation completed - revision 1 - BUI Quang Anh
 */
#include "StdAfx.h"
#include "ThinningAlgorithm.h"
#include "Tools.h"

//
unsigned char ThinningAlgorithm::MASK[3][3] =	{{0,0,0},{0,0,0},{0,0,0}};

// Constructor
ThinningAlgorithm::ThinningAlgorithm(void)
{
}

// Destructor
ThinningAlgorithm::~ThinningAlgorithm(void)
{
}


// Find image's skeleton
// @source: source image
// @dest: destination image
void ThinningAlgorithm::thinning( const IplImage *source, IplImage *dest)
{
	if (dest != source)
	{
		cvCopy(source,dest);
	}

	// Remove spurious loops in image
	//this->remove_spurious_loops(dest,dest);

	bool isModified = false;
	do
	{
		isModified = false;
		isModified = this->thinning_kernel(dest);
	}
	while(isModified);
	return;
}

// Find image's half-thinned skeleton
// @source: source image
// @dest: destination image
void ThinningAlgorithm::half_thinning(IplImage *source, IplImage *dest)
{
	if (dest != source)
	{
		cvCopy(source,dest);
	}
	
	// Remove spurious loops in image
	//this->remove_spurious_loops(dest,dest);

	// Calculate estimated stroke width
	int stroke_width = Tools::calculate_estimated_stroke_width(dest);

	// Apply thinning kernel function in (stroke_width / 2) times
	for (int i = 0; i< (int) ceil(stroke_width * 1.0 / 2) ; i++)
	{
		this->thinning_kernel(dest);
	}
	return;
}

// Check first condition used for remove border pixel
// B(p) = number of image pixels (black pixels) in 8-neighbours of p
// First condition: 2 <= B(p) <= 6
// @mask: mask pattern
bool ThinningAlgorithm::check_first_condition(unsigned char mask[3][3])
{
	int B = 0;
	unsigned char ordered_set[8] = {mask[0][1],mask[0][2],mask[1][2],mask[2][2],mask[2][1],mask[2][0],mask[1][0],mask[0][0]};
	for (int i = 0; i< 8; i++)
	{
		B+= ordered_set[i];
	}
	if ((B >= 2) && (B <= 6))
	{
		return true;
	}
	else
	{
		return false;
	}
}

// Check second condition used for remove border pixel
// Xr(p) = number of pattern [0,1] in chain x1, x2, x3, ... x8
// Return Xr(p)
// Second condition: Xr(p) == 2
// @mask: mask pattern
int ThinningAlgorithm::check_second_condition(unsigned char mask[3][3])
{
	int A = 0;
	unsigned char ordered_set[9] = {mask[0][1],mask[0][2],mask[1][2],mask[2][2],mask[2][1],mask[2][0],mask[1][0],mask[0][0], mask[0][1]};
	for (int i = 0; i< 8; i++)
	{
		if ((ordered_set[i] == 0) && (ordered_set[i+1] == 1))
		{
			A++;
		}
	}
	return A;
}

// Check third condition used for remove border pixel
// Third condition: x1 * x3 * x7 == 0
// @mask: mask pattern
bool ThinningAlgorithm::check_third_condition(unsigned char mask[3][3])
{
	if (mask[0][1] * mask[1][2] * mask[2][1] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

// Check fourth condition used for remove border pixel
// Fourth condition: x1 * x7 * x5 == 0
// @mask: mask pattern
bool ThinningAlgorithm::check_fourth_condition(unsigned char mask[3][3])
{
	if (mask[1][2] * mask[2][1] * mask[1][0] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

// Check fifth condition used for remove border pixel
// Fifth condition: x1 * x3 * x5 == 0
// @mask: mask pattern
bool ThinningAlgorithm::check_fifth_condition(unsigned char mask[3][3])
{
	if (mask[0][1] * mask[1][2] * mask[1][0] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

// Check sixth condition used for remove border pixel
// Sixth condition: x3 * x5 * x7 == 0
// @mask: mask pattern
bool ThinningAlgorithm::check_sixth_condition(unsigned char mask[3][3])
{
	if (mask[0][1] * mask[2][1] * mask[1][0] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

// Check seventh condition used for remove border pixel
// Seventh condition: One of these 2 conditions must satisfy:
// a) (x1 * x7 == 1) and (x2 + x6 != 0) and (x3 + x4 + x5 + x8 == 0)
// b) (x1 * x3 == 1) and (x4 + x8 != 0) and (x2 + x5 + x6 + x7 == 0)
// @mask: mask pattern
bool ThinningAlgorithm::check_seventh_condition(unsigned char mask[3][3])
{
	bool condition_a = false;
	bool condition_b = false;
	condition_a = ((mask[1][2] * mask[2][1]) == 1) && ((mask[0][2] + mask[2][0]) != 0) /*&& ((mask[0][2] * mask[2][0]) == 0)*/ && ((mask[0][1] + mask[0][0] + mask[1][0] + mask[2][2]) == 0);
	condition_b = ((mask[1][2] * mask[0][1]) == 1) && ((mask[0][0] + mask[2][2]) != 0) /*&& ((mask[0][0] * mask[2][2]) == 0)*/ && ((mask[0][2] + mask[1][0] + mask[2][0] + mask[2][1]) == 0);
	return (condition_a || condition_b);
}

// Check eight condition used for remove border pixel
// Eight condition: One of these 2 conditions must satisfy:
// a) (x3 * x5 == 1) and (x4 + x8 != 0) and (x1 + x2 + x6 + x7 == 0)
// b) (x5 * x7 == 1) and (x2 + x6 != 0) and (x1 + x3 + x4 + x8 == 0)
// @mask: mask pattern
bool ThinningAlgorithm::check_eighth_condition(unsigned char mask[3][3])
{
	bool condition_a = false;
	bool condition_b = false;
	condition_a = ((mask[0][1] * mask[1][0]) == 1) && ((mask[0][0] + mask[2][2]) != 0) /* && ((mask[0][0] * mask[2][2]) == 0)*/ && ((mask[1][2] + mask[0][2] + mask[2][0] + mask[2][1]) == 0);
	condition_b = ((mask[1][0] * mask[2][1]) == 1) && ((mask[0][2] + mask[2][0]) != 0) /* && ((mask[0][2] * mask[2][0]) == 0)*/ && ((mask[1][2] + mask[0][1] + mask[0][0] + mask[2][2]) == 0);
	return (condition_a || condition_b);
}


// Kernel of thinning algorithm
// Delete contour points that satisfy conditions
// @source: source image
// Output: Return true if source image is modified, else, return false
bool ThinningAlgorithm::thinning_kernel(IplImage* source)
{
	bool isModified = false;

	vector<CvPoint> deleted_points;
	deleted_points.clear();
	// Image's contour
	vector<CvPoint> contour;
	// Find source image's contour
	Tools::find_contour(source,contour);

	// FIRST SUB-ITERATION
	// For each point in the contour, process thinning algorithm
	for (int i = 0; i< (int) contour.size(); i++)
	{
		CvPoint point = contour[i];

		// Creating mask's value
		for (int k = -1; k < 2; k++)
		{
			for (int l = -1; l < 2; l++)
			{
				if ((point.y + k < 0) || (point.x + l < 0) || (point.y + k >= source->height) || (point.x + l >= source->width) )
				{
					MASK[k+1][l+1] = 0;
				}
				else
				{
					unsigned char pixel_value = (((uchar *)(source->imageData + (point.y + k) * source->widthStep))[point.x + l] == 255) ? 0 : 1;
					MASK[k+1][l+1] = pixel_value;
				}
			}
		}

		// Check conditions of first subiteration
		if (this->check_first_condition(MASK) && this->check_third_condition(MASK) && this->check_fourth_condition(MASK))
		{
			if ((this->check_second_condition(MASK) == 1) || (this->check_second_condition(MASK) == 2))
			{
				if (this->check_second_condition(MASK) == 2)
				{
					if (this->check_seventh_condition(MASK))
					{
						deleted_points.push_back(point);
						isModified = true;
					}
				}
				else
				{
					deleted_points.push_back(point);
					isModified = true;
				}
			}

		}
	}
	
	// Delete points that satisfy conditions
	for(int ipt = 0; ipt <(int) deleted_points.size(); ipt++)
	{
		CvPoint current_point = deleted_points[ipt];
		((uchar *)(source->imageData + current_point.y * source->widthStep))[current_point.x] = 255;
	}
		
	deleted_points.clear();
	

	// SECOND SUB-ITERATION
	// For each point in the contour, process thinning algorithm
	for (int i = 0; i< (int) contour.size(); i++)
	{
		CvPoint point = contour[i];

		// Creating mask values
		for (int k = -1; k < 2; k++)
		{
			for (int l = -1; l < 2; l++)
			{
				if ((point.y + k < 0) || (point.x + l < 0) || (point.y + k >= source->height) || (point.x + l >= source->width) )
				{
					MASK[k+1][l+1] = 0;
				}
				else
				{
					unsigned char pixel_value = (((uchar *)(source->imageData + (point.y + k) * source->widthStep))[point.x + l] == 255) ? 0 : 1;
					MASK[k+1][l+1] = pixel_value;
				}
			}
		}

		// Check conditions of second subiteration
		if (this->check_first_condition(MASK) && this->check_fifth_condition(MASK) && this->check_sixth_condition(MASK))
		{
			if ((this->check_second_condition(MASK) == 1) || (this->check_second_condition(MASK) == 2))
			{
				if (this->check_second_condition(MASK) == 2)
				{
					if(this->check_eighth_condition(MASK))
					{
						deleted_points.push_back(point);
						isModified = true;
					}
				}
				else
				{
					deleted_points.push_back(point);
					isModified = true;
				}
			}

		}
	}
	// Delete points that satisfy conditions
	for(int ipt = 0; ipt <(int) deleted_points.size(); ipt++)
	{
		CvPoint current_point = deleted_points[ipt];
		((uchar *)(source->imageData + current_point.y * source->widthStep))[current_point.x] = 255;
	}
	
	return isModified;
}
